package com.base.dynamicprograming;

/**
 * 152. 乘积最大子数组
 * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * @author leon
 * @date 2021年12月01日 20:48
 */
public class MaxProduct {
    /**
     * 类似于最大子数组和，但是我们在需要在过程中保存，最大，最小的两种状态，并且还要判断当前值的正负情况
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int curMax,max,curMin,min;
        curMax= curMin=0;
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            if (curMax==0){
                curMax=curMin=nums[i];

            }else if (nums[i]==0){
                curMax=curMin=0;
            }else if(nums[i]>0){
                curMax = curMax>0?curMax*nums[i]:nums[i];
                curMin = curMin<0?curMin*nums[i]:nums[i];
            }else if(nums[i]<0){
                // 注意这里值，必须要加个临时变量
                int tmp1 = curMax,tmp2=curMin;
                curMax = tmp2<0?tmp2*nums[i]:nums[i];
                curMin = tmp1>0?tmp1*nums[i]:nums[i];
            }
            max = Math.max(max,curMax);
            min = Math.min(min,curMin);
        }
        return max;
    }

    /**
     * leetcode官方题解
     * @param nums
     * @return
     */
    public int maxProduct1(int[] nums) {
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            //  找三个  当前值，当前值*上个状态最大值，当前值*上个状态最小值  的最大值
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            //  找三个  当前值，当前值*上个状态最值，当前值*上个状态最小值  的最小值
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            // 找最大
            ans = Math.max(maxF, ans);
        }
        return ans;
    }

    public static void main(String[] args) {
        new MaxProduct().maxProduct(new int[]{-4,-3,-2});
    }
}
